package xyz.scootaloo.oj.leetcode

import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/7/1 15:10
 */
class P130 {

    private fun solve(board: Array<CharArray>) {
        val column: Int = board[0].size
        val row = board.size
        val path = Array(row) { BooleanArray(column) }
        val direction = arrayOf(
            intArrayOf(0, -1),      // 左
            intArrayOf(0, 1),       // 右
            intArrayOf(-1, 0),      // 下
            intArrayOf(1, 0)        // 上
        )

        fun dfs(r: Int, c: Int, records: MutableList<Pair<Int, Int>>): Boolean {
            path[r][c] = true
            records.add(Pair(r, c))
            var noTouchBorder = (r == 0) || (r == row - 1) || (c == 0) || (c == column - 1)

            for (direct in direction) {
                val nextR = r + direct[0]
                val nextC = c + direct[1]
                if (
                    (nextR < row) && (nextR >= 0) &&
                    (nextC < column) && (nextC >= 0)
                    && (!path[nextR][nextC])
                    && (board[nextR][nextC] == 'O')
                ) {
                    if (dfs(nextR, nextC, records))
                        noTouchBorder = true
                }
            }

            return noTouchBorder
        }

        fun replace(records: MutableList<Pair<Int, Int>>) {
            for (pair in records) {
                board[pair.first][pair.second] = 'X'
            }
        }

        fun search() {
            val records = ArrayList<Pair<Int, Int>>()
            for (r in 0 until row) {
                for (c in 0 until column) {
                    if (!path[r][c] && (board[r][c] != 'X')) {
                        records.clear()
                        val rsl = dfs(r, c, records)
                        if (!rsl) {
                            replace(records)
                        }
                    }
                }
            }
        }

        search()
    }

    @Test
    fun testInput() {
        val input = arrayOf(
            charArrayOf('X', 'X', 'X', 'X'),
            charArrayOf('X', 'O', 'O', 'X'),
            charArrayOf('X', 'X', 'O', 'X'),
            charArrayOf('X', 'O', 'X', 'X'),
        )
        solve(input)
        for (line in input)
            println(line)
    }

}
